#pragma once
#include <iostream>
#include <utility>
#include <vector>

namespace lw
{
	template<class T>
	struct Hash
	{
		size_t operator()(const T& val)
		{
			return val;
		}
	};
	template<>
	struct Hash<std::string>
	{
		size_t operator()(const std::string& s)
		{
			size_t hash = 0;
			for (auto ch : s)
			{
				hash += ch;
				hash *= 31;
			}
			return hash;
		}
	};
	template<class K, class V>
	struct HashNode
	{
		std::pair<K, V> _kv;
		HashNode<K, V>* _next;
		HashNode(const std::pair<K, V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};

	template<class K, class V, class HashFunc = Hash<K>>
	class HashBucket
	{
		typedef HashNode<K, V> Node;
	public:
		HashBucket()
			:_tables(10, nullptr)
		{}
		~HashBucket()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* curr = _tables[i];
				while (curr)
				{
					Node* next = curr->_next;
					delete curr;
					curr = next;
				}
				_tables[i] = nullptr;
			}
		}
		bool Insert(const std::pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			if (_n == _tables.size())
			{
				std::vector<Node*> hs(_tables.size() * 2, nullptr);
				for (int i = 0; i < _tables.size(); i++)
				{
					Node* curr = _tables[i];
					while (curr)
					{
						Node* next = curr->_next;

						size_t pos = HashFunc()(curr->_kv.first) % hs.size();
						curr->_next = hs[pos];
						hs[pos] = curr;

						curr = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(hs);
			}

			size_t pos = HashFunc()(kv.first) % _tables.size();

			Node* node = _tables[pos];
			Node* newnode = new Node(kv);
			
			newnode->_next = node;
			_tables[pos] = newnode;
			_n++;
		}
		bool Erase(const K& key)
		{
			auto erasepos = Find(key);
			if (erasepos == nullptr)
				return false;
			size_t pos = HashFunc()(key) % _tables.size();
			Node* curr = _tables[pos];
			if (curr == erasepos)
			{
				_tables[pos] = curr->_next;
				delete curr;
			}
			else
			{
				while (curr->_next != erasepos)
					curr = curr->_next;
				Node* del = curr->_next;
				curr->_next = del->_next;
				delete del;
			}
			_n--;
			return true;
		}
		Node* Find(const K& key)
		{
			size_t pos = HashFunc()(key) % _tables.size();
			
			Node* curr = _tables[pos];
			while (curr)
			{
				if (curr->_kv.first == key)
					return curr;
				curr = curr->_next;
			}
			return nullptr;
		}
	private:
		std::vector<Node*> _tables;
		size_t _n = 0;
	};

}